Office 2013: We are unable to connect right now. Please check your network and try again later.

I ran into the same problem, found a solution, and thought I'd share it just in case it's useful to others.  OneNote 2013 was saying that it was unable to connect, and under File > Account it was saying that there was no Internet connection.  And yet, I could go to my SkyDrive account through a browser and see my notes through OneNote's web app.

What I THINK is happening is that Office 2013 is getting its Internet connectivity status from the network adapter status, rather than actually trying to connect to anything.  I believe this because my "Local Area Connection" adapter was saying "No Internet Access" despite the fact that all my browsers worked, SkyDrive through a browser worked, and other Internet-reliant applications worked.

So to fix this, I went into the Network and Sharing Center, went to Change my Adapter Settings, and then disabled my "Local Area Connection" network adapter.  I waited 20 seconds then enabled it again.  It spun up, this time saying that it DID have an Internet Connection.  From that point forward, everything worked.

I've also fixed this through a reboot with a full power off (so that the hardware gets reset).  My laptop goes from being docked to not docked all the time, and sometimes the network adapter gets confused.  Either of these approaches seems to fix the problem for me.  Hope it helps someone else.

Microsoft: If you're listening, you might send a request to the product team that they check the Internet connection by actually trying to ping a Microsoft server, rather than relying on the not-always-reliable status of the NIC.  I can't tell you how many times my NIC has said "No Internet Access" when there actually IS Internet access.  Relying on the status seems to be creating a lot of heartburn for a lot of people.

To solve the Issue you can Enable ActiveProbing and then it will be able to connect.

Here is the registry key you need to change: 

[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\services\NlaSvc\Parameters\Internet]

"EnableActiveProbing"=dword:00000001